【打卡贴】（No.004）从零开始刷LeetCode

击上方“Ahab杂货铺”，选择“置顶公众号”

技术分享第一时间送达！

---

NO.4两个排序数组的中位数

原题：

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

你可以假设 nums1 和 nums2 不同时为空。

示例 1:

nums1 = [1, 3] nums2 = [2] 中位数是 2.0

示例 2:

nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5

---

中间数就是一组数据中中间的那个数。对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中间数。题目其实挺良心是一个有序数组，如果对数据先排序，然后再进行取中值，则比较耗时。

这是从网上看到的一种快速提取中位数的算法：

1：取队首，队尾和中间的三个数，通过交换数据，使得队尾最大，中间的数据最小，队首的数据为哨兵。
2：交换中间和第2个数据，通过变换数据，使存在一个位置A，在该位置前的数据都小于哨兵，在该位置后的数据都大于或等于哨兵。
3：如果A的位置在队中之后，则更新队列为1~A，否则为A~end。并继续调用这个过程。

举例如下：
数组：3，6，2，1，9，8，0，4，5，7
经过步骤1并交换中间和第2个数的值之后，则为：
7，3，2，1，6，8，0，4，5，9；此序列中，7为哨兵
经过第一次迭代后，序列为：
4，3，2，1，6，5，0，7，8，9，此序列中，在数字7的位置是正确的。
第二次迭代则取1~7个数进行求解中位数，其中，哨兵为1。迭代之后如下：
0，1，2，3，6，5，4，7，8，9，同样的，此序列中，数字1的位置也是正确的。
第三次迭代则以第3~7个数进行求解，哨兵为5，此时，5即为中位数。

自己的解答从这种算法中的得到启发，但是写起来还是费劲一番周折。

代码如下：

        # 判断传入数组是否为空
        if nums1 is None or nums2 is None:
            return
        # 求出数组nums1、nums2的长度
        nums1_length = len(nums1)
        nums2_length = len(nums2)
        # 求出两个数组的总长度
        total_length = nums1_length + nums2_length
        # 判断是否小于0
        if total_length == 0:
            return
        # 如果数组nums2传入为空，则重新调用查询中位数，
        # 调换参数位置，数组nums1的位置是允许为空的
        if nums2_length == 0:
            return self.findMedianSortedArrays(nums2, nums1)

        left = -1
        right = -1
        nums1_Start = 0
        nums2_Start = 0
        # 循环遍历总长度一半，+1是因为range取不到总长度一半
        for i in range(int(total_length/2)+1):
            # left记录上一次循环的right值
            left = right
            # 如果nums1的记录点小于nums1的长度
            # 并(nums2的记录点大于等于nums2的长度
            # 或 nums1的记录点的值 小于 nums2记录点的值)
            if nums1_Start < nums1_length and (nums2_Start >= nums2_length or nums1[nums1_Start] < nums2[nums2_Start]):
                # 给right赋值  nums1的记录点的值，然后让nums1记录点加1
                right = nums1[nums1_Start]
                nums1_Start += 1
            else:
                # 给right赋值  nums2的记录点的值，
                # 然后让nums2记录点加1
                right = nums2[nums2_Start]
                nums2_Start += 1

        # 如果总长度 & 1 为 0 ，则使用两个数除2，
        # 即判断total_length是否为偶数
        # 也可使用total_length % 2 == 0这种判断，
        # 但是使用&号性能稍高一点
        if (total_length & 1) == 0:
            return (left+right)/2.0
        else:
            # 使用除于1.0是为了让结果为浮点数
            return right/1.0

     
  
           
        

以上的代码里已经添加了十分详细的注释，应该不难于理解，自己是不满意这段代码的，代码量很大，写起来很麻烦（毕竟自己比较懒）。

下面的代码是看到解答里代码量比较少的，但是执行速度稍微慢一点，其实这种方法自己并不是很懂，希望有小伙伴可以在留言区，说明思路。

tmp = nums1 + nums2
tmp.sort()
print (tmp)
if len(tmp)%2==1:
    return tmp[int(len(tmp)/2)]
else:
    return (tmp[int(len(tmp)/2)-1]+tmp[int(len(tmp)/2)])/2.0